class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        dct = {
            2:'abc',
            3:'def',
            4:'ghi',
            5:'jkl',
            6:'mno',
            7:'pqrs',
            8:'tuv',
            9:'wxyz'
        }

        result = []

        def traverse(i, cur):
            if i==len(digits):
                result.append(cur)
                return
            for cand in dct[int(digits[i])]:
                traverse(i+1, cur+cand)
        
        traverse(0, '')
        return list(filter(lambda e: len(e)!=0, result))

print(Solution().letterCombinations(""))